package binaryTree;

public class Codee {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		//root从上往下
		//如果遇到p或q，先遇到谁返回谁
		//root在p-q之间，root即为答案
		//root小于p-q，为了往中间靠，向右寻找,root=root.right
		//root大于p-q，为了往中间靠，向左寻找,root=root.left
		
		//只有未遇到p,q就一直遍历下去
		while(root.val!=p.val&&root.val!=q.val) {
			//如果遍历过程发现值在中间，之间退出返回root
			if(Math.min(p.val,q.val)<root.val&&root.val<Math.max(p.val,q.val)) {
				break;
			}
			root=(root.val<Math.min(p.val,q.val))?root.right:root.left;
		}
        return root;
    }
}
